package _11_位运算;

/**
 * 对于一个数的幂运算
 *      2^66次方
 *          2^33*2
 *
 *          快速幂取模，(a * b) % p = (a % p) * (b % p)
 *
 *          在快速幂的基础上，加上取模运算
 */
public class _50_Pow {

    public static void main(String[] args) {
        _50_Pow v = new _50_Pow();
    }

    // 快速幂，迭代方法
    public double myPow(double x, int n) {
        long y = n >= 0? n: -((long) n);

        double res = 1.0;
        while (y > 0) {
            if ((y & 1) == 1) {
                res *= x;
            }
            x *= x;
            y >>= 1;
        }
        return n < 0? 1 / res: res;
    }

    // 快速幂, 递归方法
    public double myPow2(double x, int n) {
        if (n == 0) return 1;
        if (n == -1) return 1 / x;
        double half = myPow2(x, n >> 1);
        half *= half;
        return (n & 1) == 0? half: half * x;
    }

    // 对于int的最大负数转转变为int负数，会出现数据溢出
    public double myPow1(double x, int n) {
        return (long) n >= 0? quickMul(x, n): 1 / quickMul(x, -(long) n);
    }

    // 快速幂的解法，能达到logn的时间复杂度
    public double quickMul(double x, long n) {
        if (n == 0) {
            return 1.0;
        }
        double value = quickMul(x, n >> 1);
        // 看n是否为奇数还是偶数
        return (n & 1) == 0? value * value: value * value * x;
    }


}
